from collections import defaultdict
from typing import Optional

from python.mypackage.TreeNode import TreeNode


class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        ans = 0
        cnt = defaultdict(int)
        cnt[0] = 1
        def dfs(node: Optional[TreeNode], s:int) -> None:
            if node is None:
                return
            nonlocal ans
            s += node.val
            ans += cnt[s-targetSum]
            cnt[s] += 1
            dfs(node.left, s)
            dfs(node.right, s)
            cnt[s] -= 1
        dfs(root, 0)
        return ans
        